Two sum

Time: O(N); Space: O(N); easy

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example 1:

Input: nums = [2, 7, 11, 15], target = 9

Output: [0, 1]

Explanation:

  • Because nums[0] + nums[1] = 2 + 7 = 9

Example 2:

Input: nums=[15, 2, 7, 11], target=9

Output: [1, 2]

Hints:

  1. A really brute force way would be to search for all possible pairs of numbers but that would be too slow. Again, it’s best to try out brute force solutions for just for completeness. It is from these brute force solutions that you can come up with optimizations.

  2. So, if we fix one of the numbers, say x, we have to scan the entire array to find the next number y which is value - x where value is the input parameter. Can we change our array somehow so that this search becomes faster?

  3. The second train of thought is, without changing the array, can we use additional space somehow? Like maybe a hash map to speed up the search?

1. Brute Force [O(N^2), O(1)]

The brute force approach is simple. Loop through each element x and find if there is another value that equals to (target - x).

2. One-pass Hash Table [O(N), O(N)]

While we iterate and inserting elements into the table, we also look back to check if current element’s complement already exists in the table.

If it exists, we have found a solution and return immediately.

[14]:

class Solution1(object):
    """
    Time: O(N). We traverse the list containing nn elements only once. Each look up in the table costs only O(1) time.
    Space: O(N). The extra space required depends on the number of items stored in the hash table,
           which stores at most nn elements.
    """
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        seen = {}
        for i, num in enumerate(nums):
            remaining = target - num
            if remaining in seen:
                return [seen[remaining], i]
            seen[num] = i
        return []

[15]:

s = Solution1()
nums = [2, 7, 11, 15]
target = 9
assert s.twoSum(nums, target) == [0, 1]
nums = nums=[15, 2, 7, 11]
target = 9
assert s.twoSum(nums, target) == [1, 2]

[16]:

class Solution2(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        for i in nums:
            j = target - i
            tmp_nums_start_index = nums.index(i) + 1
            tmp_nums = nums[tmp_nums_start_index:]
            if j in tmp_nums:
                return [nums.index(i), tmp_nums_start_index + tmp_nums.index(j)]
        return []

[17]:

s = Solution2()
nums = [2, 7, 11, 15]
target = 9
assert s.twoSum(nums, target) == [0, 1]
nums = nums=[15, 2, 7, 11]
target = 9
assert s.twoSum(nums, target) == [1, 2]